package com.dyz.swordFingerOffer;

/**
 * @author: daiyizheng
 * @date: 2021/5/29 17:08
 * @description:
 */
public class TreeLinkNodeGetNext08 {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        //判断pNode是否为空
        if(pNode==null){
            return null;
        }
        //一个节点有右子树， 返回一定是右子树 最左边的节点
        if(pNode.right!=null){
            pNode = pNode.right;
            while(pNode.left!=null){
                pNode = pNode.left;
            }
            return pNode;
        }

        //一个节点没有右子树， 返回一定是父节点
        //该节点是父节点的左孩子，找上一个父节点
        if(pNode.next!=null && pNode.next.left==pNode){
            return pNode.next;
        }
        //该节点是父节点的右孩子, 找最顶端的父节点
        while(pNode.next!= null && pNode.next.right == pNode){
            pNode = pNode.next;
        }
        return pNode.next;
    }
}
class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}